package com.practice.binarysearch;

public class MaxMinDiff {
	public int max(int[] a, int k) {
		int N = a.length;
		if (N < k || k < 2) return -1;
		
		int lo = 0;
		int hi = (a[N-1] - a[0]) / (k-1) + 1;
		
		while (hi > lo+1) {
			int mid = (hi + lo) / 2;
			if (test(a, mid, k)) {
				lo = mid;
			}
			else {
				hi = mid;
			}
		}
		
		return lo;
	}
	
	private boolean test(int[] a, int diff, int k) {
		int prev = a[0];
		int j = 1;
		for (int i=1; i<k; i++) {
			while (j<a.length && a[j] - prev < diff) j++;
			if (j >= a.length) return false;
			prev = a[j];
		}
		return true;
	}
}
